// 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

// candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 

// 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/combination-sum
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 执行用时：
// 4 ms
// , 在所有 C++ 提交中击败了
// 95.26%
// 的用户
// 内存消耗：
// 10.8 MB
// , 在所有 C++ 提交中击败了
// 42.36%
// 的用户

// 看了题解，深度优先+回溯


#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<set>
using namespace std;

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {        
        dfs(candidates,0,target);
        return res;
    }

    void dfs(vector<int>& r,int p,int target){
        if(target<0){
            return;
        }
        else if(target==0){
            res.push_back(path);
            return;
        }
        else{
            for(int i=p;i<r.size();i++){
                if(r[i]<=target){
                    path.push_back(r[i]);
                    dfs(r,i,target-r[i]);
                    path.pop_back();
                }
            }
        }
    }
};